02 Binarna piramida

Binarna piramida se formira na sledeći način:

• na vrhu se nalazi 0
• svaki sledeći red se dobija tako što se svaka cifra 0 iz prethodnog reda zameni sa 0 1, a svaka cifra 1 sa 1 0

Za svaki od m upita odrediti k-tu cifru n-tog reda piramide. Indeksi redova i cifara kreću od 1. Vremenska složenost treba da bude O(m ⋅ n), a prostorna O(1).

Ulaz

Sa standardnog ulaza se učitavaju broj m (1 ≤ m ≤ 1000), a zatim i m upita oblika n k.

Izlaz

Na standardni izlaz za svaki od m upita ispisati k-tu cifru n-tog reda piramide.

Primer

Ulaz

3
2 1
3 3
4 7

Izlaz

0
1
0